package company.divide;

import java.util.*;

/**
 * 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * <p>
 * 示例 1：
 * <p>
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 示例 2：
 * <p>
 * 输入：digits = ""
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 */
public class LetterCombinations17 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = "";
        String[] split = sc.nextLine().split("=");
        if (split.length == 1) {
            s = "";
        } else {
            s = split[1].substring(2, split[1].length() - 1);
        }
        System.out.println(letterCombinations(s));
    }

    public static List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length()==0) {
            return res;
        }

        Map<String, String> map = new HashMap<>();
        map.put("2", "abc");
        map.put("3", "def");
        map.put("4", "ghi");
        map.put("5", "jkl");
        map.put("6", "mno");
        map.put("7", "pqrs");
        map.put("8", "tuv");
        map.put("9", "wxyz");
        dfs("", digits, res, map, 0);
        return res;
    }

    /**
     * 除了与自身的那组组合，还需要和别组组合
     * @param s
     * @param digits
     * @param res
     * @param map
     * @param index
     */
    public static void dfs(String s, String digits, List<String> res, Map<String, String> map, int index) {
        if (index == digits.length()) {
            res.add(s);
            return;
        }
        String words = map.get(String.valueOf(digits.charAt(index)));
        // for循环是为了和自己一组组合
        for (int i = 0; i < words.length(); i++) {
            // 深度遍历是为了和其他组组合
            dfs(s + words.charAt(i), digits, res, map, index + 1);
        }
    }
}
